package com.lishem.carl._10dp;

import java.util.Scanner;

/**
 * 这是个ACM模式的题目，具体题目在：
 * <p>
 * https://kamacoder.com/problempage.php?pid=1046
 * <p>
 * 输入描述：
 *
 * 第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。
 *
 * 第二行包含 M 个正整数，代表每种研究材料的所占空间。
 *
 * 第三行包含 M 个正整数，代表每种研究材料的价值。
 * <p>
 * 输出描述
 *
 * 输出一个整数，代表小明能够携带的研究材料的最大价值。
 * <p>
 * 输入示例：
 * <p>
 * 6 1
 * <p>
 * 2 2 3 1 5 2
 * <p>
 * 2 3 1 5 4 3
 * <p>
 * 输出示例：
 * 5
 */
public class _8KaMaCode_01背包 {

    /**
     * 二维数组版本
     *
     * @param space  空间
     * @param weight 价值
     * @param N      背包总空间
     * @return
     */
    private static int getMaxWeight(int[] space, int[] weight, int N) {
        int[][] dp = new int[space.length][N + 1];
        for (int i = 0; i < dp[0].length; i++) {
            if (i >= space[0]) {
                dp[0][i] = weight[0];
            }
        }
        // i 表示物品数， j表示背包容量
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                if (j >= space[i]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - space[i]] + weight[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[dp.length - 1][dp[0].length - 1];
    }

    /**
     * @param space  每件物品的重量
     * @param weight 每件物品的价值
     * @param N      背包总重量
     * @return
     */
    public static int getMaxWeight1(int[] space, int[] weight, int N) {
        int[] dp = new int[N + 1];
        // 初始化
        for (int i = 0; i < dp.length; i++) {
            if (i >= space[0]) {
                dp[i] = weight[0];
            }
        }
        for (int i = 1; i < space.length; i++) {
            // 这里一定要从后往前遍历
            for (int j = N; j > 0; j--) {
                if (j >= space[i]) {
                    dp[j] = Math.max(dp[j], dp[j - space[i]] + weight[i]);
                }
            }
        }
        return dp[N];
    }


    public static void main(String[] args) {
        int[] space = new int[]{2, 2, 3, 1, 5, 2};
        int[] weight = new int[]{2, 3, 1, 5, 4, 3};
        System.out.println(getMaxWeight(space, weight, 1));
        System.out.println(getMaxWeight1(space, weight, 1));
    }


    /**
     * 处理ACM输入 main 方法
     *
     * @param args
     */
    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String str = sc.nextLine();
            //获取M 和 N
            int M = Integer.parseInt(str.split(" ")[0]);
            int N = Integer.parseInt(str.split(" ")[1]);
            //构建数组
            String[] spaceStr = sc.nextLine().split(" ");
            String[] weightStr = sc.nextLine().split(" ");
            int[] space = new int[M];
            int[] weight = new int[M];
            for (int i = 0; i < M; i++) {
                space[i] = Integer.parseInt(spaceStr[i]);
                weight[i] = Integer.parseInt(weightStr[i]);
            }
            System.out.println(getMaxWeight(space, weight, N));
        }
    }


}
